'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-22 15:50:54
'''
class Solution:
    def findMedian(self, arr, n) : 
        def recurse(arr, ord):
            tmp = arr[-1]
            i = 0
            for j, v in enumerate(arr[:-1]):
                if v<tmp:
                    arr[i], arr[j] = arr[j], arr[i]
                    i += 1
            arr[-1], arr[i] = arr[i], arr[-1]
            # print(arr, ord, arr[-1], i)
            if i > ord-1:
                return recurse(arr[:i], ord)
            elif i<ord-1:
                # print('haha', arr[i+1:])
                return recurse(arr[i+1:], ord-i-1)
            else:
                return arr[i]

        return recurse(arr[0:], n//2)
    # print("Median = " ,ans)

if __name__ == "__main__":
    arr = [ 12, 3, 5, 7, 4, 19, 26 ]
    n = len(arr)
    solution = Solution()
    print(solution.findMedian(arr, n))



